# 递归
# 将问题转化为较小规模的同类问题来解决

# 函数自己调用自己
# 一定要有一个终止条件

# n!
# 10! = 1*2*3*...*10

# 5! = 4! * 5 = 24 * 5 = 120
# 4! = 3! * 4 = 6 * 4 = 24
# 3! = 2! * 3 = 2 * 3= 6
# 2! = 1! * 2 = 1*  2 = 2
# 1! = 1

# def foo(n):
#     if n == 1:
#         return 1
#     else:
#         return foo(n-1)*n
#
# print(foo(1))
# print(foo(5))

# 栈内存
# 每调用一个函数，栈内存中就会为了这个函数开辟一块空间，栈帧。用来存放这个函数中的局部变量等信息
# 函数执行完，栈帧出栈

# 练习：编写函数，使用递归
# 1.计算 1+2+3+...n
#
# def foo(n):
#     if n == 1:
#         return 1
#     else:
#         return foo(n-1)+n
# print(foo(100))

# 2.打印斐波那契数列 0 1 1 2 3 5 8 13 21 34.。。。
#
# n = int(input("请输入数列的个数："))
# def foo(n):
#     if n == 2:
#         return 1
#     elif n == 1:
#         return 0
#     else:
#         return foo(n-1)+foo(n-2)
# for i in range(n):
#     print(foo(i+1),end=' ')


# 3. 编写阿克曼函数
# Ackermann函数定义如下：　若m=0，返回n+1。
# 若m>0且n=0，返回Ackermann(m-1,1)。
# 若m>0且n>0，返回Ackermann(m-1,Ackermann(m,n-1))

# def Ackermann(m,n):
#     if m == 0:
#         return n+1
#     elif m > 0 and n == 0 :
#         return Ackermann(m-1,1)
#     elif m > 0 and n > 0 :
#         return Ackermann(m-1,Ackermann(m,n-1))
# print(Ackermann(3,2))

# 4. 假设你在走楼梯，每次你都可以选择走一步或者两步。如果楼梯一共有n个台阶，那你爬到最高处一共有多少种不同的方式呢？

def model(n):
    if n <= 2:
        return n
    else:
        x = model(n-1)+model(n-2)
        return x
print(f'1级台阶有{model(1)}种走法')
print(f'2级台阶有{model(2)}种走法')
print(f'3级台阶有{model(3)}种走法')
print(f'4级台阶有{model(4)}种走法')
print(f'5级台阶有{model(5)}种走法')
print(f'20级台阶有{model(20)}种走法')
